This paper develops a fresh approach to the analysis of some drifting games. Our focus is on the identification of asymptotically optimal potential-based strategies for some versions of this repeated two-person game. Our approach involves (a) guessing an asymptotically optimal potential by solving an associated PDE (which is in general highly nonlinear); then (b) justifying the guess, by proving upper and lower bounds on the final-time loss whose difference scales like a negative power of the number of time steps. Our upper bounds are based on potential-based strategies for the player, and our lower bounds are similarly based on strategies for the adversary. Their proofs are rather elementary, using Taylor expansion and the explicit character of the potential. Most previous work on asymptotically optimal strategies has used potentials obtained by solving a discrete dynamic programming principle, which is complicated and sometimes intractable.

Prediction with experts' advice is one of the most fundamental problems in online learning and captures many of its technical challenges. A recent line of work has looked at online learning through the lens of differential equations and continuous-time analysis. This viewpoint has yielded optimal results for several problems in online learning. In this paper, we employ continuous-time stochastic calculus in order to study the discrete-time experts' problem. We use these tools to design a continuous-time, parameter-free algorithm with improved guarantees for the quantile regret. We then develop an analogous discrete-time algorithm with a very similar analysis and identical quantile regret bounds. Finally, we design an anytime continuous-time algorithm with regret matching the optimal fixed-time rate when the gains are independent Brownian Motions; in many settings, this is the most difficult case. This gives some evidence that, even with adversarial gains, the optimal anytime and fixed-time regrets may coincide.

Prediction with expert advice is a foundational problem in online learning. In instances with $T$ rounds and $n$ experts, the classical Multiplicative Weights Update method suffers at most $\sqrt{(T/2)\ln n}$ regret when $T$ is known beforehand. Moreover, this is asymptotically optimal when both $T$ and $n$ grow to infinity. However, when the number of experts $n$ is small/fixed, algorithms with better regret guarantees exist. Cover showed in 1967 a dynamic programming algorithm for the two-experts problem restricted to $\{0,1\}$ costs that suffers at most $\sqrt{T/2\pi} + O(1)$ regret with $O(T^2)$ pre-processing time. In this work, we propose an optimal algorithm for prediction with two experts' advice that works even for costs in $[0,1]$ and with $O(1)$ processing time per turn. Our algorithm builds up on recent work on the experts problem based on techniques and tools from stochastic calculus.

Applying neural network (NN) methods in games can lead to various With the recent boom in neural network (NN) applications, game new and exciting game dynamics not previously possible. However, designers have been increasingly exploring a variety of NN approaches they also lead to new challenges such as the lack of large, in computer games [65]. These include approaches where clean datasets, varying player skill levels, and changing gameplay a NN is directly incorporated into the gameplay experience or as a strategies. In this paper, we focus on the adversarial player strategy method for dynamically generating content that would otherwise aspect in the game iNNk, in which players try to communicate be created by a human artist [65]. This approach has been utilized secret code words through drawings with the goal of not being in well-known games such as Black and White [36], Creatures [23], deciphered by a NN. Some strategies exploit weaknesses in the NN and Forza Motosport [17], which adapt game agent behavior in response that consistently trick it into making incorrect classifications, leading to player input. In these cases, the NN makes gameplay to unbalanced gameplay. We present a method that combines more personalized and potentially more engaging.

We present a method for encoding game logs as numeric features in the card game Dominion. We then run the manifold learning algorithm t-SNE on these encodings to visualize the landscape of player strategies. By quantifying game states as the relative prevalence of cards in a player's deck, we create visualizations that capture qualitative differences in player strategies. Different ways of deviating from the starting game state appear as different rays in the visualization, giving it an intuitive explanation. This is a promising new direction for understanding player strategies across games that vary in length.

We consider the problem of influence maximization in fixed networks, for both stochastic and adversarial contagion models. The common goal is to select a subset of nodes of a specified size to infect so that the number of infected nodes at the conclusion of the epidemic is as large as possible. In the stochastic setting, the epidemic spreads according to a general triggering model, which includes the popular linear threshold and independent cascade models. We establish upper and lower bounds for the influence of an initial subset of nodes in the network, where the influence is defined as the expected number of infected nodes. Although the problem of exact influence computation is NP-hard in general, our bounds may be evaluated efficiently, leading to scalable algorithms for influence maximization with rigorous theoretical guarantees. In the adversarial spreading setting, an adversary is allowed to specify the edges through which contagion may spread, and the player chooses sets of nodes to infect in successive rounds. Both the adversary and player may behave stochastically, but we limit the adversary to strategies that are oblivious of the player's actions. We establish upper and lower bounds on the minimax pseudo-regret in both undirected and directed networks.

Serious games are popular computer games that frequently simulate real-world events or processes designed for the purpose of solving a problem. Although they are often entertaining, their main purpose is to train or educate users. Not surprisingly, users exhibit different game play behaviors because of their diverse background and game experience. To improve the educational effectiveness of these games, it is important to understand and learn from the interaction between the users and the game engine. This paper presents a study attempting to apply machine learning techniques to the game log to discover: a) strategies that are common to players interacting with serious games and b) variances in the demographics of the player base for these strategies. This is an empirical study with end-user data while playing Missing, a serious game developed to help mitigate biases that people may exhibit when analyzing plausible hypothesis for observed events. We found a set of common strategies and interesting variances in player demographics associated with these strategies.

We study the power of different types of adaptive (nonoblivious) adversaries in the setting of prediction with expert advice, under both full-information and bandit feedback. We measure the player's performance using a new notion of regret, also known as policy regret, which better captures the adversary's adaptiveness to the player's behavior. In a setting where losses are allowed to drift, we characterize ---in a nearly complete manner--- the power of adaptive adversaries with bounded memories and switching costs. In particular, we show that with switching costs, the attainable rate with bandit feedback is $\widetilde{\Theta}(T^{2/3})$. Interestingly, this rate is significantly worse than the $\Theta(\sqrt{T})$ rate attainable with switching costs in the full-information case. Via a novel reduction from experts to bandits, we also show that a bounded memory adversary can force $\widetilde{\Theta}(T^{2/3})$ regret even in the full information case, proving that switching costs are easier to control than bounded memory adversaries. Our lower bounds rely on a new stochastic adversary strategy that generates loss processes with strong dependencies.